package algorithm.sort;


import algorithm.utils.Utils;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSortDemo {

  private int[] arr;

  public static void main(String[] args) {

    int[] random = Utils.RandomArr(3);
    System.out.println(Arrays.toString(random));

    //测试
    //

    int[] arr = {70, 42, 86};
    System.out.println(Arrays.toString(arr));
    QuickSortDemo quickSortDemo = new QuickSortDemo(arr);
    quickSortDemo.sort(0, 2);
    System.out.println(Arrays.toString(quickSortDemo.arr));


  }

  public QuickSortDemo(int[] arr) {
    this.arr = arr;
  }

  /**
   * 排序
   *
   * @param lo 右指针
   * @param hi 左指针
   */
  public void sort(int lo, int hi) {

    if (lo == hi) {
      return;   //一个元素就不用比较拉
    }


    int i = lo;
    int j = hi;
    int v = this.arr[lo];//切分点

    boolean flag = false;
    while (true) {

      while (!bigThan(this.arr[++i], v)) { //右指针向左移动,直到找到比v大
        if (i == j || i == (this.arr.length - 1)) { //指针碰撞 or 越界
          flag = true;
          break;
        }
      }
      while (!bigThan(v, this.arr[j])) { //左指针向右移动,直到找到v比j大的

        if (i == j || j == 0) {
          flag = true;
          break;
        }

        j--;
      }
      if (flag) break; //指针碰撞时就退出
      exchange(i,j); //找到之后,指针所指位置互换
    }
    exchange(lo, i); //切分点 和 指针碰撞位置互换
  }

  public boolean bigThan(int lo, int hi) {
    if (lo > hi) {
      return true;
    }
    return false;
  }

  public void exchange(int k, int index) {
    int temp = this.arr[index];
    this.arr[index] = this.arr[k];
    this.arr[k] = temp;
  }


}
